class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //可以使用堆的方法解决，第二种分组递归的方法
        return quickselect(nums,k);
    }
    int quickselect(vector<int>& nums,int k)
    {
        vector<int> big,small,equal;
        //选择一个基准元素
        int pivot = nums[rand()%nums.size()];
        for(int num:nums)
        {
            if(num>pivot)
            {
                big.push_back(num);
            }
            else if(num == pivot)
            {
                equal.push_back(num);
            }
            else
            {
                small.push_back(num);
            }
        }
        if(k<=big.size())
        {
            //说明要找的第k大在big数组中
            return quickselect(big,k);
        }
        if(nums.size()-small.size()<k)
        {
            //nums.size()-small.size()代表的是大于或者等于pivot元素的数量如果是小于k的那么代表第k大在small数组中
            //但是此时去small数组中寻找的就不是第k大了，因为small前面有pivoot和big都是大于small中所有元素的
            return quickselect(small,k-(nums.size()-small.size()));
        }
        return pivot;
    }
};